﻿
int[] numbers1 = { 3, 7, 2, 9, 5 }; // 定义一个整数数组
        int sum = 0; // 初始化总和为0

        // 使用 foreach 遍历数组并累加
        foreach (int num in numbers1)
        {
            sum += num; // 将当前元素累加到 sum
        }

        Console.WriteLine("数组元素总和: " + sum); // 输出 26

        string message = "Hello, C#!"; // 定义一个字符串

        // 遍历字符串中的每个字符
        foreach (char c in message)
        {
            if (char.IsLetter(c)) // 检查当前字符是否为字母
            {
                Console.Write(c + " "); // 打印字母
            }
        }

        // 定义一个字典，存储学生姓名和分数
        Dictionary<string, int> studentScores = new Dictionary<string, int>
        {
            { "Alice", 90 },
            { "Bob", 85 },
            { "Charlie", 78 }
        };

        // 遍历字典中的键值对
        foreach (KeyValuePair<string, int> entry in studentScores)
        {
            Console.WriteLine($"{entry.Key} 的分数是 {entry.Value}");
        }
        /* 输出：
            Alice 的分数是 90
            Bob 的分数是 85
            Charlie 的分数是 78
        */

         // 定义一个商品列表
         //类在最后
        List<Product> products = new List<Product>
        {
            new Product { Name = "鼠标", Price = 99.99m },
            new Product { Name = "键盘", Price = 199.99m },
            new Product { Name = "显示器", Price = 899.99m }
        };

        // 遍历自定义对象集合
        foreach (Product product in products)
        {
            Console.WriteLine($"{product.Name} 的价格是 {product.Price:C}");
        }
        /* 输出：
            鼠标 的价格是 ￥99.99
            键盘 的价格是 ￥199.99
            显示器 的价格是 ￥899.99
        */



       // 定义一个整数数组
        int[] numbers = { 10, 20, 30, 40, 50 };

        // 使用 foreach 遍历数组并打印每个元素
        Console.WriteLine("数组元素：");
        foreach (int number in numbers)
        {
            Console.WriteLine(number);
        }

        // 定义一个字符串列表
        List<string> fruits = new List<string> { "Apple", "Banana", "Cherry", "Date" };

        // 使用 foreach 遍历列表并打印每个元素
        Console.WriteLine("水果列表：");
        foreach (string fruit in fruits)
        {
            Console.WriteLine(fruit);
        }
       

       
        // 定义地图：0=可通行，1=障碍物
        int[,] map = new int[5, 5]
        {
            { 0, 1, 0, 0, 0 },
            { 0, 1, 0, 1, 0 },
            { 0, 0, 0, 1, 0 },
            { 0, 1, 1, 1, 0 },
            { 0, 0, 0, 0, 0 }
        };

        Grid start = new Grid(0, 0); // 起点 (0,0)
        Grid end = new Grid(4, 4);   // 终点 (4,4)


        // 调用BFS算法寻找路径
        List<Grid> path = FindPath(map, start, end);

        if (path != null)
        {
            Console.WriteLine("找到路径：");
            foreach (Grid grid in path)
            {
                Console.WriteLine($"({grid.X}, {grid.Y})");
            }
        }
        else
        {
            Console.WriteLine("无可行路径！");
        }

        
    /// <summary>
    /// 使用BFS算法寻找路径
    /// </summary>
    /// <param name="map">地图</param>
    /// <param name="start">起点</param>
    /// <param name="end">终点</param>
    /// <returns>路径列表，若未找到路径则返回null</returns>
    /// 算法思想：从起点开始，逐层扩展搜索范围，直到找到终点。
    // 使用队列（FIFO）存储待探索的节点。
    //FS的特点
// 优点：

// 能找到最短路径（如果路径代价相同）。

// 适合用于无权图或网格地图的路径搜索。

// 缺点：

// 需要存储所有待探索的节点，空间复杂度较高。

// 不适合用于大规模图或树的搜索。
    static List<Grid> FindPath(int[,] map, Grid start, Grid end)
    {
        Queue<Grid> queue = new Queue<Grid>(); // 用于BFS的队列
        HashSet<string> visited = new HashSet<string>(); // 记录已访问的格子
        List<Grid> path = new List<Grid>(); // 存储最终路径

        // 初始化队列和已访问集合
        queue.Enqueue(start);//将起点加入队列，作为BFS的起始点。
        visited.Add($"{start.X},{start.Y}");//将起点的坐标（如 "0,0"）加入已访问集合，标记为已访问。

        // 定义四个方向：上、下、左、右
        int[] dx = { -1, 1, 0, 0 };//对应上、下、左、右的X偏移。
        int[] dy = { 0, 0, -1, 1 };//对应上、下、左、右的Y偏移。

        // BFS主循环
        //只要队列不为空，就继续搜索。
        //BFS需要不断从队列中取出格子并探索其相邻格子，直到找到终点或队列为空。
        while (queue.Count > 0)
        {
            Grid current = queue.Dequeue(); // 取出当前格子
            //从队列中取出一个格子，作为当前探索的格子。

            // 找到终点，回溯生成路径
            if (current.X == end.X && current.Y == end.Y)
            {
                Grid step = current;
                while (step != null) // 回溯到起点
                {
                    path.Add(step);//将当前格子加入路径列表。
                    step = step.Parent;//回溯到父节点，继续添加到路径中。
                }
                path.Reverse(); // 反转路径，从起点到终点
                return path;
                //BFS只能找到终点，但无法直接记录路径。
                // 通过 Parent 属性，可以从终点回溯到起点，生成完整路径。
            }

            // 遍历四个方向
            //简化代码，避免手动管理索引。
            foreach (int i in new int[] { 0, 1, 2, 3 })
            {
                int newX = current.X + dx[i]; // 新格子的X坐标
                int newY = current.Y + dy[i]; // 新格子的Y坐标

                // 检查新格子是否合法
                if (newX >= 0 && newX < map.GetLength(0) && // 检查X坐标是否越界
                    newY >= 0 && newY < map.GetLength(1) && // 检查Y坐标是否越界
                    map[newX, newY] == 0 && // 检查是否为可通行格子
                    !visited.Contains($"{newX},{newY}")) // 检查是否已访问
                {
                    Grid next = new Grid(newX, newY, current); // 创建新格子
                    queue.Enqueue(next); // 加入队列
                    visited.Add($"{newX},{newY}"); // 标记为已访问
                }
            }
        }

        return null; // 未找到路径
    }
    

// 定义格子坐标类
//Grid 需要包含 Parent 成员，而 Parent 的类型也是 Grid，
// 这会导致结构体循环依赖。
//类可以轻松解决这个问题，因为类是引用类型。
// 存储的是引用（指针）可以包含自身类型的成员
public class Grid
{
    public int X { get; } // 格子的X坐标
    public int Y { get; } // 格子的Y坐标
    public Grid Parent { get; } // 父节点，用于回溯路径

    // 构造函数
    public Grid(int x, int y, Grid parent = null)
    {
        X = x;
        Y = y;
        Parent = parent; // 父节点默认为null
    }
}

// // 定义一个商品列表
        class Product
{
    public string Name { get; set; } // 商品名称
    public decimal Price { get; set; } // 商品价格
}




